package 数据结构.树;

import java.util.Stack;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-01
 */
public class JZ54二叉搜索树的第k个节点 {
    //递归中序遍历
    //记录返回的节点
    private TreeNode res = null;
    //记录中序遍历了多少个
    private int count = 0;
    public void midOrder(TreeNode root, int k){
        if(root==null || count>k)
            return;
        midOrder(root.left,k);
        count++;
        if(count==k)
            res = root;
        midOrder(root.right,k);
    }
    public int KthNode (TreeNode proot, int k) {
        // write code here
        midOrder(proot,k);
        if(res!=null)
            return res.val;
        return -1;
    }

    //非递归中序遍历
    public int KthNode2 (TreeNode proot, int k) {
        if(proot==null)
            return -1;
        int cnt = 0;
        TreeNode p = null;
        Stack<TreeNode> s = new Stack<>();
        while (!s.isEmpty()||proot!=null){
            while (proot!=null){
                s.push(proot);
                proot = proot.left;
            }
            p = s.pop();
            cnt++;
            if(cnt==k)
                return p.val;
            proot = p.right;
        }
        return -1;
    }
}
